Programmable logic devices (PLDs) typically make use of one or more interconnect arrays that are programmed via an array of memory cells (e.g., EPROM, EEPROM Flash EPROM or Flash EEPROM cells) to make the various interconnections within the PLD that are specific to a desired design. Because advances in the art allow regular increases in the complexity of PLDs, the size of the programmable interconnect array must also be increased to achieve the desired PLD complexity.
Unfortunately, a problem exists in assigning signals to routes or paths provided by the programmable interconnect array in the PLD. U.S. Pat. No. 5,563,528, entitled, Multiplexer for Programmable Logic Device, to Diba et al., illustrates an example of a programmable interconnect array for which routing signals may be difficult. Specifically, an interconnect-multiplexer (XMUX) is used to direct signals to a plurality of function blocks in a PLD. The XMUX has multiple input resources, each of which is connectable to at least three output resources. Therefore, the problem is one of assigning the multiple signals that are required for various ones of the function blocks to the available input and output resources of the XMUX. A successful assignment requires that all the signals be assigned to paths provided by the XMUX, such that the functional blocks will receive the required signals.
A prior method for assigning signals to XMUX paths does so on a function block by function block basis. The method first orders function blocks by the number of input signals required by the function block. The function block requiring the most input signals is processed first. That is, signals required by this function block are assigned to XMUX paths first. Since the signals associated with the last function block to be processed will be the most difficult to assign to XMUX paths, it is desirable to save the function block needing the fewest signals until last.
If all of the signals required by one function block could not be assigned to paths of the XMUX, then a version of the Hungarian algorithm is applied to signals required by the function block such that signals are reassigned to different XMUX paths. The Hungarian algorithm is described in "Applied and Algorithmic Graph Theory" by Chartrand and Oellermann, McGraw Hill. If the Hungarian algorithm fails to assign all signals to paths of the XMUX for the function block, then the assignment process has failed. It will be appreciated that even though there may be a combination of assignments of signals to XMUX paths that results in all signals being assigned, present methods are not sophisticated enough to redo signal assignments between function blocks.
Therefore, while prior methods sometimes function effectively to assign signals to input/output resources of an interconnect array, they sometimes are unable to assign all signals, even though such a solution exists. A method that addresses the aforementioned problems is therefore desirable.